//给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
//如果 needle 不是 haystack 的一部分，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "sadbutsad", needle = "sad"
//输出：0
//解释："sad" 在下标 0 和 6 处匹配。
//第一个匹配项的下标是 0 ，所以返回 0 。
// 
//
// 示例 2： 
//
// 
//输入：haystack = "leetcode", needle = "leeto"
//输出：-1
//解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= haystack.length, needle.length <= 10⁴ 
// haystack 和 needle 仅由小写英文字符组成 
// 
//
// Related Topics 双指针 字符串 字符串匹配 👍 1901 👎 0


package leetcode.editor.cn;

// [28]找出字符串中第一个匹配项的下标

public class FindTheIndexOfTheFirstOccurrenceInAString_28 {
    public static void main(String[] args) {
        Solution solution = new FindTheIndexOfTheFirstOccurrenceInAString_28().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int strStr(String haystack, String needle) {
            if (haystack == null || haystack.length() == 0 || needle == null || needle.length() == 0 || needle.length() > haystack.length()) {
                return -1;
            }
            int[] nextArr = getNextArray(needle.toCharArray());
            int x = 0, y = 0;
            while (x < haystack.length() && y < needle.length()) {
                if (haystack.charAt(x) == needle.charAt(y)) {
                    x++;
                    y++;
                } else if (nextArr[y] == -1) {
                    x++;
                } else {
                    y = nextArr[y];
                }
            }
            return y == needle.length() ? x - y : -1;
        }

        public int[] getNextArray(char[] str) {
            if (str.length == 1) {
                return new int[]{-1};
            }
            int[] nextArr = new int[str.length];
            nextArr[0] = -1;
            nextArr[1] = 0;
            int i = 2;
            int cn = 0;
            while (i < str.length) {
                if (str[i - 1] == str[cn]) {
                    nextArr[i++] = ++cn;
                } else if (cn > 0) {
                    cn = nextArr[cn];
                } else {
                    nextArr[i++] = 0;
                }
            }
            return nextArr;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}